package solution.medium;

import java.util.Arrays;
import java.util.Random;

/**
 * @Program: solution
 * @Description: leetcode-200. 岛屿数量
 * @Author: Mr.Yiu
 * @CreatedTime: 2021-10-14 10:41
 * https://leetcode-cn.com/problems/number-of-islands/
 **/
public class Find_island {

    public static void main(String[] args) {
        char[][] grid = new char[10][10];
        Random r = new Random();
        for (int i = 0; i < grid.length ; i++) {
            for (int j = 0; j < grid[0].length ; j++) {
                if(r.nextInt(2)<1){
                    grid[i][j] = '0';
                }else{
                    grid[i][j] = '1';
                }
            }
        }

//        System.out.println(Arrays.deepToString(grid));
        for (int i = 0; i < grid.length; i++) {
            System.out.println(Arrays.toString(grid[i]));
        }
        System.out.println("岛屿数量：" + numIslands(grid));
    }

    public static int numIslands(char[][] grid) {
        int count = 0; //岛屿数量

//        if(grid==null || grid.length==0 || grid[0].length==0)
//            return count;

        int row = grid.length;
        int col = grid[0].length;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]=='1'){
                    count++;
                    combine(grid, i, j);
                }
            }
        }

        return count;
    }

    public static void combine(char[][] grid, int row, int col){
        grid[row][col] = '2';//标记过修改值

        if(row > grid.length-1 && col > grid[0].length-1)
            return ;//二维数组以外

        if(row < grid.length-1 && grid[row+1][col]=='1'){//向下
            grid[row+1][col] = '2';
            combine(grid,row+1, col);
        }

        if(col < grid[0].length-1 && grid[row][col+1]=='1'){//向右
            grid[row][col+1] = '2';
            combine(grid,row, col+1);
        }

        if(row > 0 && grid[row-1][col]=='1'){//向上
            grid[row-1][col] = '2';
            combine(grid,row-1, col);
        }

        if(col > 0 && grid[row][col-1]=='1'){//向左
            grid[row][col-1] = '2';
            combine(grid,row, col-1);
        }

    }
}
